package 每日一题;

import java.util.*;

public class No1122数组的相对排序 {

    /**
     * 给你两个数组，arr1 和 arr2，
     * arr2 中的元素各不相同
     * arr2 中的每个元素都出现在 arr1 中
     * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
     * 未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
     *
     * 示例：
     * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
     * 输出：[2,2,2,1,4,3,3,9,6,7,19]
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {

        List<Integer> list=new ArrayList<>();
        Set<Integer> set=new HashSet<>(arr2.length);
        for (int i : arr2) {
            set.add(i);
        }
        Map<Integer,Integer> map=new HashMap<>();//值:次数
        for (int i : arr1) {
            if(set.contains(i)){
                map.put(i,map.getOrDefault(i,0)+1);
            }else{
                list.add(i);
            }
        }
        int[] arr3=new int[arr1.length];
        int index=0;
        for (Integer key : arr2) {
            Integer count = map.get(key);
            for (Integer i = 0; i < count; i++) {
                arr3[index++]=key;
            }
        }

        list.sort(Comparator.comparing(Integer::intValue));

        for (Integer integer : list) {
            arr3[index++]=integer;
        }

        return arr3;
    }

}
